/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class MyCalendarIII {
	// class Node {
	// int left, right;
	// int count;
	// }
	//
	// Node root;
	int[] arr;
	static final int maxVal = 1000000000;

	int maxK = 0;

	public MyCalendarIII() {
		// 建立线段树
		arr = new int[maxVal + 1];
	}

	public int book(int start, int end) {
		find(start, end, 0, maxVal, 0);
		return maxK;
	}

	private void find(int start, int end, int left, int right, int index) {
		if (left >= right) {
			arr[index]++;
			maxK = Math.max(maxK, arr[index]);
			return;
		}
		int mid = (left + right) >> 1;
		if (end <= mid) {
			find(start, end, left, mid, index << 1);
		} else if (start > mid) {
			find(start, end, mid + 1, right, (index << 1) + 1);
		} else {
			find(start, mid, left, mid, index << 1);
			find(mid + 1, end, mid + 1, right, (index << 1) + 1);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MyCalendarIII MyCalendarThree = new MyCalendarIII();
		System.out.println(MyCalendarThree.book(10, 20)); // returns 1
		MyCalendarThree.book(50, 60); // returns 1
		System.out.println(MyCalendarThree.maxK);
		MyCalendarThree.book(10, 40); // returns 2
		System.out.println(MyCalendarThree.maxK);
		MyCalendarThree.book(5, 15); // returns 3
		System.out.println(MyCalendarThree.maxK);
		MyCalendarThree.book(5, 10); // returns 3
		MyCalendarThree.book(25, 55); // returns 3
		System.out.println(MyCalendarThree.maxK);

	}

}
